//面试题 17.10 主要元素
//如果数组中多一半的数都是同一个，则称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。 
//
// 示例 1： 
//
// 输入：[1,2,5,9,5,9,5,5,5]
//输出：5 
//
// 
//
// 示例 2： 
//
// 输入：[3,2]
//输出：-1 
//
// 
//
// 示例 3： 
//
// 输入：[2,2,1,1,1,2,2]
//输出：2 
//
// 
//
// 说明： 
//你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？ 
// Related Topics 位运算 数组 分治算法


package leetcode.editor.cn;

class A面试题1710FindMajorityElementLcci {
    public static void main(String[] args) {
        Solution solution = new A面试题1710FindMajorityElementLcci().new Solution();
        System.out.println("佛祖保佑");
        System.out.println("\uD80C\uDC09\uD80C\uDC02\uD80C\uDC03\uD80C\uDC10");

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 解答成功:
     * 执行耗时:1 ms,击败了100.00% 的Java用户
     * 内存消耗:43.3 MB,击败了100.00% 的Java用户
     */
    class Solution1 {
        public int majorityElement(int[] nums) {
            int temp = 0;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (count == 0) {
                    //先前的元素两两消除了，存下本元素即可
                    temp = nums[i];
                    count = 1;
                    continue;
                }
                if (nums[i] == temp) {
                    count++;
                } else {
                    count--;
                }
            }

            count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == temp) {
                    count++;
                }
            }
            if (count > nums.length / 2) {
                return temp;
            }
            return -1;


        }
    }

    /**
     * 解答成功:
     * 执行耗时:1 ms,击败了100.00% 的Java用户
     * 内存消耗:43.3 MB,击败了100.00% 的Java用户
     */
    class Solution {
        public int majorityElement(int[] nums) {
            int temp = nums[0];
            int count = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == temp) {
                    count++;
                } else {
                    count--;
                    if (count == 0) {
                        temp = nums[i];
                        count = 1;
                    }
                }
            }

            count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == temp) {
                    count++;
                }
            }
            if (count > nums.length / 2) {
                return temp;
            }
            return -1;


        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
